The generalized random dot product graph is a random graph model in which each vertex \(v_i\) has a corresponding hidden vector \(x_i \in \mathbb{R}^{p+q}\) and each edge probability is the indefinite inner product of the corresponding pair of hidden vectors, i.e., \(P_{ij} = x_i^\top I_{p, q} x_j\), \(I_{p,q} = \Bigl[\begin{smallmatrix} I_{p} & 0 \\ 0 & - I_{q} \end{smallmatrix} \Bigr]\)
Approximate \(A\) by spectral decomposition \(A \approx V_{p, q} \Lambda_{p, q} V_{p, q}^\top\). The subscript \(p, q\) denotes the \(p\) most positive and \(q\) most negative eigenvalues and corresponding eigenvectors. Each \(\hat{x}_i\), the \(i^{th}\) row of \(\hat{X} = V_{p, q} |\Lambda_{p, q}|^{1/2},\) estimates the relative position of its corresponding latent vector \(x_i\), up to an indefinite orthogonal transformation.
Theorem (Rubin-Delanchy et al. 2022): \(\max_i \| \hat{x}_i - Q_n x_i \| = O_P \Big( \frac{\log^c n}{n^{1/2}} \Big)\) for some \(Q_n \in \mathbb{O}(p, q)\).
It has been previously shown that the SBM, DCBM, and PABM are GRDPGs in which the communities lie on point masses, line segments, and subspaces, respectively.
Let \(p, q \geq 0\), \(d = p + q \geq 1\), \(1 \leq r < d\), \(K \geq 2\), and \(n > K\) be integers. Define manifolds \(\mathcal{M}_1, ..., \mathcal{M}_K \in \mathcal{X}\) for \(\mathcal{X} = \{x, y \in \mathbb{R}^d : x^\top I_{p,q} y \in [0, 1]\}\) each by continuous function \(g_k : [0, 1]^r \to \mathcal{X}\). Define probability distribution \(F\) with support \([0, 1]^r\). Then the following mixture model is a manifold block model:
Block models can be expressed as GRDPGs in which the communities are linear structures in the latent space. We propose the manifold block model to characterize nonlinear latent structures and the \(K\)-curves clustering algorithm to estimate these structures for community detection.